In satellite communications, mobile telecommunication systems, or the like, an error correction encoding technique exhibiting a large encoding gain is employed in order to satisfy requirements in terms of the system structures such as reduction of required power, reduction in the size of antennas, and the like. In such case, low density parity check (LDPC) codes are known as an error correction codes exhibiting a large encoding gain, and more and more of the LDPC codes are employed to various kinds of communications systems described above or to storage devices of magnetic recording.
The low density parity check codes do not simply show a single error correction encoding method but is a general name for error correction codes having such a character that a check matrix is sparse (most components in a matrix are “0”, and the number of component “1” is extremely small).
Through selecting a check matrix in a sparse state, it is possible to structure an error correction encoding method having a large encoding gain by using a repeat decoding method such as sum-product algorithm or a min-sum algorithm (see Non-Patent Documents 1, 2, for example).
Here, a block matrix of r×n is shown in Expression 1 (r, n are natural numbers satisfying r≦n). In each component of the block matrix shown in FIG. 1, Ii, j shows a cyclic replacement matrix or zero matrix of m×m (symbol m is a natural number, symbol i is an integer between 0 and r−1, and symbol j is an integer between 0 and n−1).
                    H        =                  [                                                                      I                                      0                    ,                    0                                                                                                I                                      0                    ,                    1                                                                              …                                                              I                                      0                    ,                                          n                      -                      1                                                                                                                                            I                                      1                    ,                    0                                                                                                I                                      1                    ,                    1                                                                              …                                                              I                                      1                    ,                                          n                      -                      1                                                                                                                          …                                            …                                            …                                            …                                                                                      I                                                            r                      -                      1                                        ,                    0                                                                                                I                                                            r                      -                      1                                        ,                    1                                                                              …                                                              I                                                            r                      -                      1                                        ,                                          n                      -                      1                                                                                                    ]                                    [                  Expression          ⁢                                          ⁢          1                ]            
The low density parity check encoding having the block matrix of Expression 1 as a check matrix is particularly called m-stage quasi-cyclic parity check codes. That is, a set of sequences whose matrix product with the matrix H is zero among all the information sequence of n×m bits is the m-stage quasi-cyclic parity check codes constituted with a frame length=n×m and a check matrix=H.
Regarding the sum-product and min-sum algorithm as the decoding methods of the low density parity check codes, decoding processing and the device for achieving the processing tend to become complicated as the stage number m becomes smaller with respect to the natural number n.
Therefore, it is possible to extend the frame length while suppressing the complication of the decoding processing by increasing the size m with the above-described cyclic replacement matrix Ii, j. However, with the low density parity check codes of such structure in general, a large increase in the encoding gain in accordance with the increase in the frame length cannot be expected.
There is Patent Document 1 described in the followings as a related technique regarding an error correction encoding apparatus which generates low density parity check codes from an input information sequence by using a low density parity check matrix. The technique depicted in Patent Document 1 includes a module which outputs the low density parity check matrix which is structured to continue a row in which cyclic replacement matrix in the same number as the weight of the row is arranged for the number of rows satisfying the prescribed weight distribution, and to gradually increase or decrease the weight of the row. This is designed to improve the performance compared to the methods using random number sequence.    Non-Patent Document 1: Robert Gallager “Low-Density Parity-Check Codes” pp. 21-28, IEEE Transactions On Information Theory, January 1962    Non-Patent Document 2: D. J. C Mackay, “Good Error-Correcting Codes Based On Very Sparse Matrices” pp. 399-431, IEEE Transactions On Information Theory, March 1999    Patent Document 1: WO2006/106841